//计算连通分量
//两个点之间存在路径，那么他们是连通的
//和并查集不完全一样，但是确实是深度优先遍历
//给每个连通分量分配一个标识符identifier，这样使得查询保持在constant time
//基本上就是对图的每个节点进行遍历，深度优先遍历，然后对同一组深度优先遍历的（也就是一个连通分量内的），分配同一个id
public class CC {
    boolean marked[];
    int id[];
    int count;
    //找到G中的连通分量
    public CC(Graph g)
    {
       marked=new boolean[g.V()];
       id=new int[g.V()];
       count=0;
       for(int i=0;i<g.V();i++)
       {
        if(!marked[i])
        {
          Dfs(g, i);
          count++;
        }
       }
    }

    public void Dfs(Graph g,int v)
    {
        marked[v]=true;
        for(int i:g.adj(v))
        {
           if(!marked[i])
           {
            marked[i]=true;
            id[i]=count;
            Dfs(g,i);
           }
        }
    }

    //判断是否连通
    public boolean IsConnected(int i,int v)
    {
      return id[i]==id[v];
    }

    //有多少连通分支
    public int count()
    {
      return count+1;
    }

    //返回v的id
    public int id(int v)
    {
        return id[v];
    }
 
}
